Trước khi hoàn thành Age of Empires, Ensemble Studios đã ký một hợp đồng với Microsoft cho phần tiếp theo. Nhóm thiết kế đã chọn để thiết lập The Age of Kings trong thời Trung Cổ là một sự tiến triển hợp lý từ thiết lập thời cổ đại của Age of Empires. Nhóm thiết kế đã có ý thức cố gắng để nắm bắt sự hấp dẫn rộng rãi của trò chơi đầu tiên mà không làm cho thiết kế của trò chơi quá giống. Tuy nhiên, họ đã cố gắng để thu hút số lượng lớn người chơi Age of Empires.[25]

Nhóm thiết kế của The Age of Kings dự định hoàn thành trò chơi trong vòng một năm bằng cách sử dụng mã từ bản gốc và tái sử dụng engine trò chơi.[26] Một vài tháng vào quá trình nhóm nhận thấy họ sẽ không thể hoàn thành trò chơi với đầy đủ chất lượng trong thời gian đó. Ensemble Studios do đó thông báo cho Microsoft là họ sẽ cần thêm một năm và thay vào đó tạo ra Age of Empires: The Rise of Rome, bản mở rộng dễ dàng phát triển của Age of Empires, như một sự thỏa hiệp choi việc được phát hành cho Giáng sinh năm 1998.[25] Để giúp đáp ứng thời hạn vào năm tới, nhóm huy động thêm nhiều lập trình viên, nghệ sĩ, và nhà thiết kế.[27]

Age of Empires bị chỉ trích vì trí tuệ nhân tạo (AI). Bởi vì nếu AI không "ăn gian" [28] bằng cách được cấp một nguồn tài nguyên bổ sung hơn người chơi hoặc sử dụng các kỹ thuật khác mà người chơi không có được, nó dễ bị đánh bại hơn nhiều so với phần trí tuệ nhân tạo của nhiều trò chơi chiến lược thời gian thực khác. Đối với The Age of Kings, Ensemble Studios đã cố gắng phát triển một hệ thống AI mạnh hơn mà không bằng cách gian lận. Nhà phát triển kì cựu trong ngành công nghiệp game là Mario Grimani đã dẫn dắt Ensemble Studios trong việc tạo ra hệ thống mới. Ở chế độ tiêu chuẩn, AI không ăn gian. Tuy nhiên, ở các mức độ cao hơn như vừa phải, khó, và khó nhất, AI được cung cấp một lượng tài nguyên tại một số thời điểm khác nhau.

Để khắc phục một nhược điểm đáng kể khác của Age of Empires là tìm kiếm đường đi, nhóm phát triển đã thiết kế lại hoàn toàn hệ thống di chuyển trong engine của trò chơi.[27]

Nhóm phát triển đã ít thành công hơn trong việc giải quyết các vấn đề khác; lập trình viên Matt Pritchard phàn nàn sau khi phát hành Age of Empires là vẫn không có quá trình mà các bản vá lỗi có thể được ban hành. Sự gian lận xảy ra rộng rãi trong phần chơi mạng của Age of Empires là một kết quả của một số lỗi trong các trò chơi, và kết quả là Microsoft hứa hẹn Ensemble Studios sẽ có một quá trình vá lỗi cho The Age of Kings. Trong khi phát hành, có một số lỗi cần chú ý ngay lập tức, nhưng quá trình vá lỗi vẫn chưa sẵn sàng. Các bản vá đầu tiên được phát hành 11 tháng sau đó.[29][30]

Ensemble Studios đã phát triển một hệ thống địa hình mới cho The Age of Kings, với khả năng thể hiện 3D tốt hơn Age of Empires. Pritchard lưu ý một sự cải thiện trong khả năng nghệ thuật của nhóm làm việc của 2 trò chơi trong quá khứ và ông ghi nhận bằng nói rằng "AOK đã trở thành một giới thiệu cho tài năng cải thiện của họ".[27] Tuy nhiên, ông lại phàn nàn về việc thiếu một công cụ quản lý tài sản nghệ thuật, trong khi các phòng ban khác đã đạt được các công cụ mới và các bước tự động để hỗ trợ trong thiết kế và chơi thử nghiệm.[27][29]

The Age of Kings chứng kiến sự ra đời của một hệ thống kích hoạt cho trình soạn thảo kịch bản của nó. Hệ thống đã cho phép các tin nhắn được hiển thị, hoặc các hành động đang diễn ra, dựa trên tiêu chí cài đặt trước hoặc "sự kiện".[31] Biên tập kịch bản cũng được cải thiện bởi hệ thống AI mới. Các hệ thống AI và kích hoạt tương tác thường xuyên trong các chiến dịch chơi đơn.[32]

Nhạc nền cho The Age of Kings do Stephen Rippy đạo diễn, người cũng thực hiện công việc này cho tất cả các trò chơi trong loạt Age of Empires. Âm nhạc cho trò chơi được chia thành hai loại. Đối với âm nhạc "trong trò chơi", nhóm nghiên cứu của Rippy lấy yếu tố âm nhạc từ nhiều nền văn hóa và kết hợp chúng để tạo ra một âm thanh hỗn hợp. Âm nhạc "trước khi chơi" được thiết kế đặc trưng cho mỗi nền văn minh. Chiến dịch dựa trên các số liệu lịch sử sẽ bao gồm "một nhà chủ đề ít nhất sẽ được bắt nguồn từ văn hóa [của nhân vật]".[33]

Một bản demo của The Age of Kings được phát hành vào ngày 16 tháng 10 năm 1999.[35] Nó minh họa chiến dịch hướng dẫn, một mẫu của một trò chơi random map, và khả năng để chơi thông qua MSN Gaming Zone [30]. Tuy nhiên Ensemble Studios đã thất vọng vì nhiều phiên bản không đầy đủ của trò chơi đã bị rò rỉ. Chúng được chọn bởi các trang web warez và bán bất hợp pháp trong suốt Bờ Thái Bình Dương; phiên bản warez của trò chơi thậm chí còn được bán bên ngoài văn phòng của Microsoft tại Hàn Quốc[29].